287. Find the Duplicate Number

Similar Question

Solution Tips

方案一: 快慢指针 (判圈算法)

var findDuplicate = function(nums) {
	// 与 442 相比就是不能修改原数组
	// 又要求 O(n) , 所以只能用判圈算法, 然后就是无法找出全部的重复数了
	// 只能知道哪个重复了
    let slow = 0, fast = 0;
    do {
        slow = nums[slow];
        fast = nums[nums[fast]];
    } while (slow != fast);
    slow = 0;
    while (slow != fast) {
        slow = nums[slow];
        fast = nums[fast];
    }
    return slow;
};

方案二: 二分查找

分析

关键：这道题的关键是对要定位的“数”做二分，而不是对数组的索引做二分。要定位的“数”根据题意在 1 和 n 之间，每一次二分都可以将搜索区间缩小一半。

以 [1, 2, 2, 3, 4, 5, 6, 7] 为例，一共有 8 个数，每个数都在 1 和 7 之间。1 和 7 的中位数是 4，遍历整个数组，统计小于 4 的整数的个数，至多应该为 3 个，

• 如果超过 3 个就说明重复的数存在于区间 [1,4) （注意：左闭右开）中
• 否则，重复的数存在于区间 [4,7]（注意：左右都是闭）中

这里小于 4 的整数有 4 个（它们是 1, 2, 2, 3），因此砍掉右半区间，连中位数也砍掉。

以此类推，最后区间越来越小，直到变成 1 个整数，这个整数就是我们要找的重复的数。

实现

var findDuplicate = function (nums) {
    const len = nums.length
    let min = 1, max = len - 1
    while (min < max) {
        const mid = (min + max) >>> 1
        let counter = 0
        for (let i = 0; i < len; i++) {
            if (nums[i] <= mid) {
                counter++
            }
        }
        if (counter > mid) {
            max = mid
        } else {
            min = mid + 1
        }
    }
    return min
}
  
let nums = [1, 2,  3, 4, 5, 6,6, 7]
console.log(findDuplicate(nums))